#ifndef LRU_CACHE_H
#define LRU_CACHE_H

#include <cstddef>
#include <optional>
#include <stdexcept>
#include <unordered_map>
#include <utility>
#include <list>

template<typename K, typename V>
class LRUCache{
public:
    using KVPair = std::pair<K, V>;

    explicit LRUCache(size_t capacity) : capacity(capacity){
        if (!capacity) {
            throw std::invalid_argument("capacity must be > 0");
        }
    }

    bool get(const K& key, V& value);
    std::optional<V> get(const K& key);
    void put(const K& key, const V& value);
    bool erase(const K& key);
    
    size_t size() const {
        return list.size();
    }

    size_t capacit() const {
        return capacity;
    }

    void clear() {
        map.clear();
        list.clear();
    }

private:
    size_t capacity;
    std::list<KVPair> list;
    std::unordered_map<K, typename std::list<KVPair>::iterator> map;
};

template<typename K, typename V>
bool LRUCache<K,V>::get(const K& key, V& value){
    auto it = map.find(key);
    if (it == map.end()) {
        return false;
    }

    list.splice(list.begin(),list,it->second);
    value = it->second->second;
    return true;
}

template<typename K, typename V>
std::optional<V> LRUCache<K,V>::get(const K& key){
    auto it = map.find(key);
    if (it == map.end()) {
        return std::nullopt;
    }

    list.splice(list.begin(),list,it->second);
    return it->second->second;
}

template<typename K, typename V>
void LRUCache<K,V>::put(const K& key, const V& value){
    auto it = map.find(key);
    if (it != map.end()) {
        it->second->second = value;
        list.splice(list.begin(),list,it->second);
    }else {
        if (list.size() >= capacity) {
            auto& old = list.back();
            map.erase(old.first);
            list.pop_back();
        }
        list.emplace_front(key,value);
        map[key] = list.begin();
    }
}

template<typename K, typename V>
bool LRUCache<K,V>::erase(const K& key){
    auto it = map.find(key);
    if (it == map.end()) {
        return false;
    }
    list.erase(it->second);
    map.erase(it);
    return true;
}

#endif